package leetcode.offer_two_special.string;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/VabMRr/
 *
 * @author mazouri
 * @create 2021-09-05 23:17
 */
public class _15_findAnagrams {
    /**
     * @param s
     * @param p 子串
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        ArrayList<Integer> counts = new ArrayList<>();
        if (s.length() < p.length()) return counts;

        int[] letters = new int[26];
        for (int i = 0; i < p.length(); i++) {
            letters[p.charAt(i) - 'a']++;
            //将初始的设置为-1
            letters[s.charAt(i) - 'a']--;
        }

        if (allZero(letters)) counts.add(0);

        for (int i = p.length(); i < s.length(); i++) {
            letters[s.charAt(i) - 'a']--;
            letters[s.charAt(i - p.length()) - 'a']++;

            if (allZero(letters)) counts.add(i - p.length() + 1);
        }

        return counts;
    }

    private boolean allZero(int[] letters) {
        for (int letter : letters) {
            if (letter != 0) return false;
        }
        return true;
    }
}
